#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
using namespace std;

/*
 *这个就是对数器的模板代码，可以用来测试题目
 * */

// 正确算法（暴力解法）

// 待测试算法（Kadane算法）
int BubbleSort(vector<int> &nums) {
  for (int i = nums.size() - 1; i >= 0; --i) {
    for (int j = 0; j <= i - 1; ++j) {
      if (nums[j] > nums[j + 1]) {
        swap(nums[j], nums[j + 1]);
      }
    }
  }
  return 0;
}
// 随机数组生成器
vector<int> generateRandomArray(int max_size, int min_val, int max_val) {
  int size = rand() % max_size + 1; // 保证至少1个元素
  vector<int> arr(size);
  for (int i = 0; i < size; ++i) {
    arr[i] = rand() % (max_val - min_val + 1) + min_val;
  }
  return arr;
}

int main() {
  srand(time(0)); // 设置随机种子
  const int TEST_TIMES = 100;
  const int MAX_SIZE = 100;
  const int MIN_VAL = -100;
  const int MAX_VAL = 100;

  for (int i = 0; i < TEST_TIMES; ++i) {
    vector<int> arr = generateRandomArray(MAX_SIZE, MIN_VAL, MAX_VAL);
    vector<int> a = arr;
    vector<int> b = arr;
    BubbleSort(a);
    std::sort(b.begin(), b.end());
    for (int i = 0; i < arr.size(); ++i) {
      if (a[i] != b[i]) {
        cout << "error" << endl;
        cout << "Your: " << endl;
        for (int j = 0; j < a.size(); ++j) {
          cout << a[j] << " ";
          if (j == a.size() - 1) {
            cout << endl;
          }
        }
        cout << "Right:" << endl;
        for (int j = 0; j < b.size(); ++j) {
          cout << b[j] << " ";
          if (j == b.size() - 1) {
            cout << endl;
          }
        }
        cout << "Oring:" << endl;
        for (int j = 0; j < arr.size(); ++j) {
          cout << arr[j] << " ";
          if (j == arr.size() - 1) {
            cout << endl;
          }
        }
	return 1;
      }
    }
  }

  cout << "所有 " << TEST_TIMES << " 次测试通过！" << endl;
  return 0;
}
